/**
 * Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, 
find the largest rectangle containing all ones and return its area.
 */
package com.xinpan.exercise;

public class MaximumRectangle {
    public int maximalRectangle(char[][] matrix) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(matrix.length == 0)
            return 0;
        int h = matrix.length;
        int w = matrix[0].length;

        int[][] cnt = new int[h][w];
        
        for(int i = 0; i < h; i++)
            if(matrix[i][0] == '1')
                cnt[i][0] = 1;
            else
                cnt[i][0] = 0;
                
        for(int i = 0; i < h; i++)
            for(int j = 1; j < w; j++)
            {
                if(matrix[i][j] == '1')
                    cnt[i][j] = cnt[i][j-1]+1;
                else
                    cnt[i][j] = 0;
            }
            
        int max = 0;
        for(int i = h-1; i >= 0; i--)
        {
            for(int j = w-1; j >= 0; j--)
            {
                if(cnt[i][j] * (i+1) > max)
                {
                    int k = i;
                    int min = cnt[i][j];
                    int tmp = cnt[i][j];
                    for(;k >= 0 && cnt[k][j] != 0; k--)
                    {
                        if(cnt[k][j] < min)
                            min = cnt[k][j];
                        
                        if((i-k+1) * min > tmp)
                            tmp = (i-k+1) * min;
                    }
                    if( tmp > max)
                        max = tmp;
                }
            }
        }
        return max;
    }
    
    public static void main(String[] args)
    {
    	MaximumRectangle mr	= new MaximumRectangle();
    	char[][] matrix = {{'1','0'},{'0','1'},{'0','1'},{'0','1'},
    			{'1','1'},{'0','0'},{'0','1'}};
    	
    	System.out.println(mr.maximalRectangle(matrix));
    }
}
